package MyDFS;

import java.util.ArrayList;
import java.util.List;

public class Leetcode0797 {
    public static List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<>();
        int len = graph.length;
        path.add(0);
        dfs(graph, 0, len, path, res);
        return res;
    }
    public static void dfs(int[][] graph, int cur, int len, List<Integer> path, List<List<Integer>> res){
        if(cur == len - 1){
            res.add(path);
            System.out.println(path);
            return;
        }
        for(int index: graph[cur]){
            List<Integer> newPath = new ArrayList<>(path);
            newPath.add(index);
            dfs(graph, index, len, newPath, res);
        }
    }


    public static void main(String[] args) {
//        int[][] graph = {{1,2}, {3}, {3}, {}};
        int[][] graph = {{4,3,1},{3,2,4},{3},{4},{}};
        allPathsSourceTarget(graph);
    }
}
